package C051;

import java.util.PriorityQueue;

/**
 * ClassName: C06
 * Package: C051
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/3/13 10:56
 * @Version 1.0
 * @Since 1.0
 */
public class C06 {
    // 对数器测试
    public static void main(String[] args) {
        System.out.println("测试开始");
        int N = 50;
        int V = 30;
        int M = 3000;
        int testTime = 20000;
        for (int i = 0; i < testTime; i++) {
            int n = (int) (Math.random() * N) + 1;
            int[] arr = randomArray(n, V);
            int m = (int) (Math.random() * M);
            int ans1 = binaryProcess(arr, m);
            int ans2 = heapProcess(arr, m);
            if (ans1 != ans2) {
                System.out.println("出错了!");
            }
        }
        System.out.println("测试结束");
    }

    // 堆模拟
    // 验证方法，不是重点
    // 如果m很大，该方法会超时
    // 时间复杂度O(m * log(n))，额外空间复杂度O(n)
    public static int waitingTime1(int[] arr, int m) {
        // 一个一个对象int[]
        // [醒来时间，服务一个客人要多久]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            heap.add(new int[] { 0, arr[i] });
        }
        for (int i = 0; i < m; i++) {
            int[] cur = heap.poll();
            cur[0] += cur[1];
            heap.add(cur);
        }
        return heap.peek()[0];
    }

    // 对数器测试
    public static int[] randomArray(int n, int v) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (int) (Math.random() * v) + 1;
        }
        return arr;
    }



    public static int heapProcess(int[] arr, int m) {
        // 建立小跟堆
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        for (int i = 0; i < arr.length; i++) {
            heap.add(new int[]{0, arr[i]});
        }

        for (int i = 0; i < m; i++) {
            int[] poll = heap.poll();
            poll[0] += poll[1];
            heap.add(poll);
        }
        int[] peek = heap.peek();
        return peek[0];
    }


    // 二分答案法解决
    public static int binaryProcess(int[] arr, int m) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            min = Math.min(min, arr[i]);
        }

        int l = 0, r = min * m, mid, count, res = 0;
        while(l <= r) {
            mid = l + ((r - l) >> 1);
            count = process(arr, mid);
            if(count < m + 1) {
                l = mid + 1;
            } else {
                r = mid - 1;
                res = mid;
            }
        }
        return res;
    }

    // process 在mid 的时间下能服务多少人
    private static int process(int[] arr, int mid) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            ans += (mid / arr[i]) + 1;
        }
        return ans;
    }


}
